//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 
//
// 回文串 是正着读和反着读都一样的字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
// 
//
// 示例 2： 
//
// 
//输入：s = "a"
//输出：[["a"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 16 
// s 仅由小写英文字母组成 
// 
// Related Topics 字符串 动态规划 回溯 👍 1303 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * [P131]_分割回文串
 *
 * @author cjl
 * @date 2022-11-03 20:58:05
 */
public class P131_PalindromePartitioning {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P131_PalindromePartitioning().new Solution();
        System.out.println("args = ".substring(0,1));
    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public List<List<String>> partition(String s) {
            int[][] flag = new int[s.length()][s.length()];
            List<List<String>> resList = new ArrayList<>();
            partition(s, new ArrayList<>(), 0, resList, flag);
            return resList;
        }

        public void partition(String s, List<String> currList,int pre,List<List<String>> resultList,int[][] flag){
            if(pre == s.length()){
                resultList.add(new ArrayList<>(currList));
                return;
            }
            for(int i = pre + 1; i <= s.length(); i++){
                if(isHuiwen(s,pre, i - 1, flag)){
                    currList.add(s.substring(pre, i));
                    partition(s, currList, i,resultList, flag);
                    currList.remove(currList.size()-1);
                }
            }
        }

        public boolean isHuiwen(String s, int start, int end,int[][] flag) {
            if(start == end){
                return true;
            }
            if(s.charAt(start) != s.charAt(end)){
                flag[start][end] = -1;
                return false;
            }
            if(start == end +1 ){
                flag[start][end] = 1;
                return true;
            }
            if(flag[start +1][end -1] == -1){
                flag[start][end] = -1;
                return false;
            }
            return isHuiwen(s, start+1, end-1, flag);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}